package SGGStu;


/**
 * @Author: Dijah
 * @Date: 2023/3/9 10:32
 * @Desc: 堆排序
 */
public class heapSortDemo {

    public static int [] heapSort(int[] arr){
        if(arr == null || arr.length == 0){
            return arr;
        }
        //建堆
        for(int i = arr.length - 1; i >= 0; i--){
            //排序
            heapify(arr,i,arr.length);
        }
        int heapSize = arr.length;
        swap(arr,0,--heapSize);
        while (heapSize > 0){
            heapify(arr,0,heapSize);
            swap(arr,0,--heapSize);
        }
        return arr;
    }

    private static void heapify(int[] arr, int index, int heapSize) {
        //左孩子节点
        int left = index * 2 + 1;
        while (left < heapSize){
            //储存子结点中更大的数的下标 (有右比大，没右左大)
            int larger = ((left+1<heapSize) && (arr[left+1]>arr[left])) ? (left+1) : left;
            //父节点和较大孩子之间进行比较
            int largest = arr[index]>arr[larger] ? index : larger;
            if (largest == index) { //若父节点已经比子节点都大，则大根堆结构已完成
                break;
            }
            swap(arr, index, largest);
            index = largest;
            left = 2*index+1;
        }
    }

    public static void swap(int[] arr, int i1, int i2) {
        int tmp = arr[i1];
        arr[i1] = arr[i2];
        arr[i2] = tmp;
    }

    public static void main(String[] args) {
        int [] arr = {5,4,3,2,1};
        int[] ints = heapSort(arr);
        for (int i = 0; i < ints.length; i++) {
            System.out.println(ints[i]);
        }
    }


}
